import java.io.IOException;
import java.util.Stack;

public class Dijkstra
{
    public static void main(String[] args) throws IOException
    {
        final Integer VERTEX_COUNTS = 6;
        final Integer Vs = 0;// 起始顶点
        Integer  min=0, node_id = 0;
        Stack<Integer> S_Stack = new Stack<Integer>();
        Integer[] Dist = new Integer[VERTEX_COUNTS];// 起始顶点到各顶点距离

        Matrix mMatrix = new Matrix(VERTEX_COUNTS, true);
        mMatrix.setMatrixItemValue(1, 5, 5);
        mMatrix.setMatrixItemValue(0, 5, 10);
        mMatrix.setMatrixItemValue(0, 2, 100);
        mMatrix.setMatrixItemValue(0, 3, 30);
        mMatrix.setMatrixItemValue(5, 4, 50);
        mMatrix.setMatrixItemValue(3, 4, 20);
        mMatrix.setMatrixItemValue(3, 2, 60);
        mMatrix.setMatrixItemValue(4, 2, 10);

        for (int i = 0; i < VERTEX_COUNTS; i++)
        {
            Dist[i] = mMatrix.Matrix[Vs][i];
        }

        while (S_Stack.size()!=VERTEX_COUNTS)
        {
            min= Integer.MAX_VALUE;
            for (int i = 0; i < Dist.length; i++)
            {
                if (S_Stack.contains(i))
                    continue;
                if (Dist[i] < min)
                {
                    node_id = i;
                    min = Dist[i];
                }
            }
            if (min== Integer.MAX_VALUE) break;
            S_Stack.push(node_id);
           
            // 更新 Dist
            for (int i = 0; i < Dist.length; i++)
            {
                if (mMatrix.Matrix[node_id][i] != Integer.MAX_VALUE)  
                {
                    if (Dist[node_id] + mMatrix.Matrix[node_id][i] < Dist[i])
                        Dist[i] = Dist[node_id] + mMatrix.Matrix[node_id][i];
                }
            }
        }
        System.out.println(S_Stack);
        System.out.print(Arrays.asList(Dist));
    }

}

class Matrix
{
    private Integer       VERTEX_COUNTS;
    public Integer[][]    Matrix = null;
    private boolean       HasDirection;//是否是有向图

    public Matrix(Integer vertex_counts, boolean direction)
    {
        this.VERTEX_COUNTS = vertex_counts;
        this.HasDirection = direction;

        this.Matrix = new Integer[VERTEX_COUNTS][VERTEX_COUNTS];

        for (int i = 0; i < Matrix.length; i++)
        {
            for (int j = 0; j < Matrix[i].length; j++)
            {
                if (i == j)
                    Matrix[i][j] = 0;
                else
                    Matrix[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    public void setMatrixItemValue(Integer i, Integer j, Integer iValue)
    {
        Matrix[i][j] = iValue;
        if (!HasDirection)
            Matrix[j][i] = iValue;
    }
}